package 力扣._00周赛._115双周赛.题目3;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    //回溯
    void backtrack(int n, List<Integer> index, int now, String[] words, int[] groups, List<Integer> max) {
        //剪枝
        //当前最优
        int max_now = index.size() + n - now;
        if (max_now <= max.size())
            return;
        if (index.size() >= 2) {
            int a = index.get(index.size() - 2);
            int b = index.get(index.size() - 1);
            if (groups[a] == groups[b] || words[a].length() != words[b].length()) {
                return;
            }
            int d_han = 0;
            for (int i = 0; i < words[a].length() && i < words[b].length(); i++) {
                if (words[a].charAt(i) != words[b].charAt(i)) {
                    d_han++;
                    if (d_han != 1)
                        return;
                }
            }
        }
        //结束条件
        if (now == n) {
            if (max.size() < index.size()) {
                max.clear();
                max.addAll(index);
            }
            return;
        }
        //回溯
        backtrack(n, index, now + 1, words, groups, max);
        index.add(now);
        backtrack(n, index, now + 1, words, groups, max);
        index.remove(index.size() - 1);
    }

    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        List<Integer> index = new ArrayList<>();
        List<Integer> max = new ArrayList<>();
        backtrack(n, index, 0, words, groups, max);
        List<String> r = new ArrayList<>();
        for (Integer i : max) {
            r.add(words[i]);
        }
        return r;
    }

    public static void main(String[] args) {
        int n = 3;
        String[] words = new String[]{"bab", "dab", "cab"};
        int[] groups = new int[]{1, 2, 2};
        List<String> wordsInLongestSubsequence = new Solution().getWordsInLongestSubsequence(n, words, groups);
        System.out.println(wordsInLongestSubsequence);
    }
}
